1. Field of the Invention
The present invention relates to the field of computer graphics and, in particular, to a system and method for performing non-affine deformations.
2. Description of the Related Art
One core functional aspect of animation, simulation, or rendering applications is converting geometric and/or mathematical descriptions of objects into images. This process is known in the industry as “rendering.” For movies or other feature films, a user (known as an animator) specifies the geometric description of objects (e.g., characters) by assigning poses and/or applying motions to the objects or to portions of the objects. Additionally, the animator may perform various transformations and/or deformations to the objects or to portions of the objects.
As is known, many graphics applications allow for a graphics scene to be represented as a hierarchy of objects. In a typical graphics application, the hierarchy includes one or more nodes connected to one another with links. In some conventional graphics applications, a parent node in the hierarchy may be connected to one or more child nodes that inherit the characteristics of the parent node. In other embodiments, the hierarchy may define a top-down geometric representation of the character, where each node defines further structural details of the character. For example, a “torso” node may be a parent node that is connected to child nodes such as a “left arm” node, a “right arm” node, a “left leg” node, and a “right leg” node. The left arm node, for example, may then be a parent node that is connected to child nodes such as “finger” nodes. This type of geometrical hierarchy is commonly referred to as a “transform hierarchy.”
One feature of transform hierarchies is the ability to perform affine transformations. An affine transform typically includes performing linear transformations, such as rotating, scaling, shearing, or translating, to the geometry that comprise the nodes in the transform hierarchy. Affine transformations are typically carried out by applying a transformation matrix to points that define the geometry being transformed.
Another feature of some graphics applications is the ability to create a different type of hierarchy for rendering the scene known as a “data flow graph.” The nodes that make up the data flow graph may represent atomic computations that are to be performed on some portion of the geometry. The nodes may then be strung together, forming the data flow graph. The input to the data flow graph may be the unaltered and untransformed object, while the output of the data flow graph may be the output object that has been modified by passing through one or more computational nodes. In some prior art systems, data flow graphs are used to perform “non-affine” transformations to the geometry in the scene. Non-affine transformation operators, also referred to herein as “movers” and “deformers,” modify or mold the shape of geometry in a non-linear fashion. For example, an animated character may be defined by a mesh of primitives that represents the skin of the character. As the underlying joints of the character move, the skin changes shape and deforms based on the movement of the joints. The deformations in the skin are often non-linear and may be represented by a non-affine operator in a data flow graph.
One problem with performing non-affine transformations using a conventional data flow graph is that the deforming process is very inefficient. In a typical situation, there may be hundreds or thousands of atomic computations strung together in a data flow graph to perform a single non-affine transformation of a singe object, causing the non-affine transformation to be computationally expensive. Since the computations that make up the non-affine transformation are geometric computations, many of the computations occur in a particular coordinate space. Some computational operators are executed in a first coordinate space, while other computational operators are executed in a second coordinate space. Additionally, in conventional approaches, the results of computations must be propagated downward and affect subsequent computations on the data flow graph. These inherent constraints on traditional data flow graph approaches create classical inefficiencies, where data must be passed through the entirety of the data flow graph and may be converted between different coordinate spaces several times to accommodate the various coordinate spaces of the particular operators being executed. Since the computational operators cannot make assumptions about other computations that are being performed downstream, certain computations are performed in case another operator may require certain data. This redundancy in computation adds further complexity and adds to the inefficiency of conventional data flow graph approaches.
As the foregoing illustrates, there is a need in the art for an improved technique for performing non-affine transformations.